package leetcode_day._2023._11;

import general_class.TreeNode;

/**
 * 1457. 二叉树中的伪回文路径
 * 算法: 深度优先搜索 + 位运算
 *
 * @author yezh
 * @date 2023/11/25 23:02
 */
public class _25 {

    int ans;

    public int pseudoPalindromicPaths(TreeNode root) {
        ans = 0;
        dfs(root, 0);
        return ans;
    }

    void dfs(TreeNode node, int cnt) {
        cnt ^= (1 << node.val);
        if (node.left == null && node.right == null && (cnt == (cnt & -cnt))) ++ans;
        if (node.left != null) dfs(node.left, cnt);
        if (node.right != null) dfs(node.right, cnt);
    }

}
